package problems

import (
	"fmt"
	"math"
	"sort"
	"strconv"
)

// 605
// https://leetcode-cn.com/problems/can-place-flowers/
func CanPlaceFlowers(flowerbed []int, n int) bool {
	place := func(n int, left, right bool) int {
		var res = (n + 1) / 2
		if !left && !right {
			return res
		}
		if n%2 == 1 || (left && right) {
			return res - 1
		}
		return res
	}
	var left, res, numZero = false, 0, 0
	for _, v := range flowerbed {
		if v == 1 {
			res += place(numZero, left, true)
			left, numZero = true, 0
		} else {
			numZero++
		}
	}
	return res+place(numZero, left, false) >= n
}

// 606
// https://leetcode-cn.com/problems/construct-string-from-binary-tree/
func Tree2str(t *TreeNode) string {
	var str = ``
	if t == nil {
		return str
	}
	str += strconv.Itoa(t.Val)
	if t.Left != nil || t.Right != nil {
		str += `(`
		str += Tree2str(t.Left)
		if t.Right != nil {
			str += `)`
			str += `(`
			str += Tree2str(t.Right)
		}
		str += `)`
	}
	return str
}

// 617
// https://leetcode-cn.com/problems/merge-two-binary-trees/
func MergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	} else if t2 == nil {
		return t1
	}
	t1.Val += t2.Val
	t1.Left = MergeTrees(t1.Left, t2.Left)
	t1.Right = MergeTrees(t1.Right, t2.Right)
	return t1
}

// 622
// https://leetcode-cn.com/problems/design-circular-queue/
type MyCircularQueue struct {
	queue []int
	size  int
}

func MyCircularQueueConstructor(k int) MyCircularQueue {
	return MyCircularQueue{queue: make([]int, 0), size: k}
}

func (mc *MyCircularQueue) EnQueue(value int) bool {
	if mc.IsFull() {
		return false
	}
	mc.queue = append(mc.queue, value)
	return true
}

func (mc *MyCircularQueue) DeQueue() bool {
	if mc.IsEmpty() {
		return false
	}
	mc.queue = mc.queue[1:]
	return true
}

func (mc *MyCircularQueue) Front() int {
	if mc.IsEmpty() {
		return -1
	}
	return mc.queue[0]
}

func (mc *MyCircularQueue) Rear() int {
	if mc.IsEmpty() {
		return -1
	}
	return mc.queue[len(mc.queue)-1]
}

func (mc *MyCircularQueue) IsEmpty() bool {
	return len(mc.queue) == 0
}

func (mc *MyCircularQueue) IsFull() bool {
	return len(mc.queue) == mc.size
}

// 628
// https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
func MaximumProduct(nums []int) int {
	sort.Ints(nums)
	var newNums = []int{}
	for _, v := range nums {
		if v != 0 {
			newNums = append(newNums, v)
		}
	}
	var length = len(newNums)
	if length < 3 {
		return 0
	}
	var res1, res2 = newNums[length-1] * newNums[length-2] * newNums[length-3], newNums[0] * newNums[1] * newNums[length-1]
	if res1 < res2 {
		res1 = res2
	}
	return res1
}

// 633
// https://leetcode-cn.com/problems/sum-of-square-numbers/
func JudgeSquareSum(c int) bool {
	var a, b = 0, int(math.Sqrt(float64(c)))
	var tmp int
	for a <= b {
		tmp = a*a + b*b
		if tmp > c {
			b--
		} else if tmp < c {
			a++
		} else {
			return true
		}
	}
	return false
}

// 637
// https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
func AverageOfLevels(root *TreeNode) []float64 {
	var res []float64
	var num []float64
	var order func(root *TreeNode, level int)
	order = func(root *TreeNode, level int) {
		if root != nil {
			if len(num) < level {
				num, res = append(num, 0), append(res, 0)
			}
			res[level-1] = (res[level-1]*num[level-1] + float64(root.Val)) / (num[level-1] + 1)
			num[level-1]++
			order(root.Left, level+1)
			order(root.Right, level+1)
		}
	}
	order(root, 1)
	return res
}

// 641
// https://leetcode-cn.com/problems/design-circular-deque/
type MyCircularDeque struct {
	queue []int
	size  int
}

func MyCircularDequeConstructor(k int) MyCircularDeque {
	return MyCircularDeque{queue: make([]int, 0), size: k}
}

func (mc *MyCircularDeque) InsertFront(value int) bool {
	if mc.IsFull() {
		return false
	}
	mc.queue = append([]int{value}, mc.queue...)
	return true
}

func (mc *MyCircularDeque) InsertLast(value int) bool {
	if mc.IsFull() {
		return false
	}
	mc.queue = append(mc.queue, value)
	return true
}

func (mc *MyCircularDeque) DeleteFront() bool {
	if mc.IsEmpty() {
		return false
	}
	mc.queue = mc.queue[1:]
	return true
}

func (mc *MyCircularDeque) DeleteLast() bool {
	if mc.IsEmpty() {
		return false
	}
	mc.queue = mc.queue[:len(mc.queue)-1]
	return true
}

func (mc *MyCircularDeque) GetFront() int {
	if mc.IsEmpty() {
		return -1
	}
	return mc.queue[0]
}

func (mc *MyCircularDeque) GetRear() int {
	if mc.IsEmpty() {
		return -1
	}
	return mc.queue[len(mc.queue)-1]

}

func (mc *MyCircularDeque) IsEmpty() bool {
	return len(mc.queue) == 0
}

func (mc *MyCircularDeque) IsFull() bool {
	return len(mc.queue) == mc.size
}

// 643
// https://leetcode-cn.com/problems/maximum-average-subarray-i/
func FindMaxAverage(nums []int, k int) float64 {
	if k > len(nums) {
		return 0
	}
	var sum, maxSum = 0, 0
	for i := 0; i < k; i++ {
		sum += nums[i]
	}
	maxSum = sum
	for i := k; i < len(nums); i++ {
		sum += nums[i] - nums[i-k]
		if maxSum < sum {
			maxSum = sum
		}
	}
	return float64(maxSum) / float64(k)
}

// 645
// https://leetcode-cn.com/problems/set-mismatch/
func FindErrorNums(nums []int) []int {
	var res []int
	var index int
	for i := 0; i < len(nums); i++ {
		index = int(math.Abs(float64(nums[i]))) - 1
		fmt.Println(index)
		if nums[index] < 0 {
			res = append(res, -nums[index])
			continue
		}
		nums[index] = nums[index]
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] > 0 {
			res = append(res, i+1)
		}
	}
	fmt.Println(nums)
	return res
}

// 653 TODO
// https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
func FindTarget(root *TreeNode, k int) bool {
	if root == nil {
		return false
	}
	var res = make(map[int]int)
	var stack = []*TreeNode{root}
	for len(stack) > 0 {
		var node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if _, ok := res[k-node.Val]; ok {
			return true
		}
		res[node.Val]++
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return false
}

// 657
// https://leetcode-cn.com/problems/robot-return-to-origin/
func JudgeCircle(moves string) bool {
	var x, y = 0, 0
	for _, v := range moves {
		switch v {
		case 'U':
			y--
		case 'D':
			y++
		case 'L':
			x--
		case 'R':
			x++
		}
	}
	return x == 0 && y == 0
}

// 661
// https://leetcode-cn.com/problems/image-smoother/
func ImageSmoother(M [][]int) [][]int {
	var res [][]int
	var getNum = func(m, n int) int {
		num, count := 0, 0
		for i := m - 1; i <= m+1; i++ {
			for j := n - 1; j <= n+1; j++ {
				if i >= 0 && j >= 0 && i < len(M) && j < len(M[0]) {
					num, count = num+M[i][j], count+1
				}
			}
		}
		return num / count
	}
	for i := 0; i < len(M); i++ {
		res = append(res, []int{})
		for j := 0; j < len(M[0]); j++ {
			res[i] = append(res[i], getNum(i, j))
		}
	}
	return res
}

// 665
// https://leetcode-cn.com/problems/non-decreasing-array/
func CheckPossibility(nums []int) bool {
	var left, right = 0, len(nums) - 1
	for i := 1; i < len(nums); i++ {
		if nums[i] < nums[i-1] {
			break
		}
		left = i
	}
	for i := len(nums) - 2; i >= left; i-- {
		if nums[i] > nums[i+1] {
			break
		}
		right = i
	}
	if right-left > 1 {
		return false
	}
	if left == right || left == 0 || right == len(nums)-1 {
		return true
	}
	return nums[left] <= nums[right+1] || nums[right] >= nums[left-1]
}

// 669
// https://leetcode-cn.com/problems/trim-a-binary-search-tree/
func TrimBST(root *TreeNode, L int, R int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val < L {
		return TrimBST(root.Right, L, R)
	} else if root.Val > R {
		return TrimBST(root.Left, L, R)
	} else {
		root.Left = TrimBST(root.Left, L, R)
		root.Right = TrimBST(root.Right, L, R)
		return root
	}
}

// 671
// https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
func FindSecondMinimumValue(root *TreeNode) int {
	if root == nil || root.Left == nil {
		return -1
	}
	var min, secondMin = root.Val, root.Left.Val
	var stack = []*TreeNode{root}
	var node *TreeNode
	for len(stack) > 0 {
		node, stack = stack[0], stack[1:]
		if node.Left != nil {
			stack = append(stack, node.Left, node.Right)
		}
		if (node.Val < secondMin && node.Val != min) || secondMin == min {
			secondMin = node.Val
		}
		if secondMin == min+1 {
			return secondMin
		}
	}
	if secondMin != min {
		return secondMin
	}
	return -1
}

// 674
// https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
func FindLengthOfLCIS(nums []int) int {
	l, max := 0, 0
	for i := 0; i < len(nums); i++ {
		if i == 0 || nums[i] <= nums[i-1] {
			l = 1
		} else {
			l++
		}

		if l > max {
			max = l
		}
		if max >= len(nums)-1-i+l {
			break
		}
	}
	return max
}

// 680
// https://leetcode-cn.com/problems/valid-palindrome-ii/
func ValidPalindrome(s string) bool {
	var isValid func(s string, sum int) bool
	isValid = func(s string, sum int) bool {
		var left, right = 0, len(s) - 1
		for left < right {
			if s[left] == s[right] {
				left++
				right--
			} else {
				if sum == 0 {
					return false
				}
				return isValid(s[:left]+s[left+1:], sum-1) || isValid(s[:right]+s[right+1:], sum-1)
			}
		}
		return true
	}
	return isValid(s, 1)
}

// 682
// https://leetcode-cn.com/problems/baseball-game/
func CalPoints(ops []string) int {
	stack, sum, num := make([]int, 0), 0, 0
	for _, v := range ops {
		switch v {
		case `+`:
			num = stack[len(stack)-1] + stack[len(stack)-2]
			stack = append(stack, num)
		case `D`:
			num = stack[len(stack)-1] * 2
			stack = append(stack, num)
		case `C`:
			num, stack = -stack[len(stack)-1], stack[:len(stack)-1]
		default:
			num, _ = strconv.Atoi(v)
			stack = append(stack, num)
		}
		sum += num
	}
	return sum
}

// 687
// https://leetcode-cn.com/problems/longest-univalue-path/
func LongestUniValuePath(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var findPath func(root *TreeNode, val int) int
	var max = 0
	findPath = func(root *TreeNode, val int) int {
		if root == nil {
			return 0
		}
		var left, right = findPath(root.Left, root.Val), findPath(root.Right, root.Val)
		if left < right {
			left, right = right, left
		}
		if max < left+right {
			max = left + right
		}
		if root.Val == val {
			return left + 1
		}
		return 0
	}
	findPath(root, root.Val)
	return max
}

// 690
// https://leetcode-cn.com/problems/employee-importance/
func GetImportance(employees []*Employee, id int) int {
	m := make(map[int]*Employee)
	for _, v := range employees {
		m[v.Id] = v
	}
	if _, ok := m[id]; !ok {
		return 0
	}
	total := 0
	var sum func(e *Employee)
	sum = func(e *Employee) {
		total += e.Importance
		e.Importance = 0
		for _, v := range e.Subordinates {
			if ee, ok := m[v]; ok {
				sum(ee)
			}
		}
	}
	sum(m[id])
	return total
}

// 693
// https://leetcode-cn.com/problems/binary-number-with-alternating-bits/
func HasAlternatingBits(n int) bool {
	num := 1 & n
	n = n >> 1
	for n > 0 {
		if num == 1&n {
			return false
		}
		n, num = n>>1, 1&n
	}
	return true
}

// 695
// https://leetcode-cn.com/problems/max-area-of-island/
func maxAreaOfIsland(grid [][]int) int {
	area, maxArea := 0, 0
	h, w := len(grid), len(grid[0])
	var dfs func(x, y int)
	dfs = func(x, y int) {
		area++
		grid[x][y] = 2
		if x > 0 && grid[x-1][y] == 1 {
			dfs(x-1, y)
		}
		if x < h-1 && grid[x+1][y] == 1 {
			dfs(x+1, y)
		}
		if y > 0 && grid[x][y-1] == 1 {
			dfs(x, y-1)
		}
		if y < w-1 && grid[x][y+1] == 1 {
			dfs(x, y+1)
		}
	}

	for x, arr := range grid {
		for y, v := range arr {
			if v == 1 {
				dfs(x, y)
				if maxArea < area {
					maxArea = area
				}
				area = 0
			}
		}
	}

	return maxArea
}

// 696
// https://leetcode-cn.com/problems/count-binary-substrings/
func CountBinarySubstrings(s string) int {
	var pre byte
	var sum, preN, curN float64
	for i := 0; i < len(s); i++ {
		if i == 0 || pre != s[i] {
			preN, curN, sum = curN, 0, sum+math.Min(preN, curN)
		}
		pre, curN = s[i], curN+1
	}
	sum += math.Min(preN, curN)
	return int(sum)
}

// 697
// https://leetcode-cn.com/problems/degree-of-an-array/
func FindShortestSubArray(nums []int) int {
	type node struct {
		size  int
		left  int
		right int
	}
	nodes, max, length := make(map[int]*node), 0, len(nums)
	for k, v := range nums {
		if _, ok := nodes[v]; !ok {
			nodes[v] = &node{
				size:  0,
				left:  k,
				right: 0,
			}
		}
		nodes[v].size++
		nodes[v].right = k
		if nodes[v].size > max {
			max = nodes[v].size
		}
	}
	for _, v := range nodes {
		if v.size == max && length > v.right-v.left+1 {
			length = v.right - v.left + 1
		}
	}
	return length
}

// 700
// https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
func SearchBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val > val {
		return SearchBST(root.Left, val)
	}
	if root.Val < val {
		return SearchBST(root.Right, val)
	}
	return root
}
